package com.nanbei.dp;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @ClassDescription: 动态规划（完全背包问题） 物品可以无限次选取，但总重量仍受限制
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/5 15:29
 */
public class KnapsackProblemComplete {

    static class Item {
        int index;
        String name;
        int weight;
        int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item(" + name + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, "青铜", 2, 3),    // c
                new Item(2, "白银", 3, 4),    // s
                new Item(3, "黄金", 4, 7),    // a
        };
        System.out.println(select(items, 6));
        System.out.println(select2(items, 6));
    }
     /*
            0   1   2   3   4   5   6
        1   0   0   c   c   cc  cc  ccc
        2   0   0   c   s   cc  cs  ccc
        3   0   0   c   s   a   a   ac
     */

    private static int select(Item[] items, int total) {
        int length = items.length;
        // 定义一个二维数组来确定背包可以存放的最大价值
        // 列代表背包可以承受的重量；
        // 行代表可以放入背包物品的品种数： 例如 为0的时候只能放入items[0]的物品 为1的时候可以方法items[0] 和 items[1] 两种物品
        int[][] dp = new int[length][total + 1];

        // 初始化第一列数据 即背包中只能存放青铜这一种物品
        for (int i = 0; i < total + 1; i++) {
            Item item = items[0];
            // 只有当背包的容量 >= 物品的容量时才能放进去该物品
            if (i >= item.weight) {
                // 因为物品可以被选取多次 当背包容量较大时 拿当前物品的价值 + 背包剩余容量可以存放的最大价值
                dp[0][i] = item.value + dp[0][i - item.weight];
            }
        }
        print(dp);

        // 初始化数组完成以后开始遍历其它物品
        for (int i = 1; i < items.length; i++) {
            Item item = items[i];
            for (int j = 1; j < total + 1; j++) {
                if (j >= item.weight){
                    // 背包的容量 >= 物品的容量时
                    //  dp[i-1][j] 上一次同容量时背包存放的最大价值
                    //  dp[i][j-item.weight]+item.value   背包剩余的容量的最大价值 +当前物品的最大价值
                    dp[i][j] =Math.max(dp[i-1][j], dp[i][j-item.weight]+item.value);
                }else {
                    // 背包当前的容量无法放下该物品 则将上一次背包存放的最大价值赋值上去
                    dp[i][j] = dp[i-1][j];
                }
            }
            print(dp);
        }
        return dp[length-1][total];
    }


    // 在二维数组的前提下降维至一维数组
    private static int select2(Item[] items, int total) {
        int[] dp = new int[total + 1];

        for (Item item : items) {
            for (int j = 1; j < total + 1; j++) {
                if (j >= item.weight) {
                    // 背包的容量 >= 物品的容量时
                    //  dp[i-1][j] 上一次同容量时背包存放的最大价值
                    //  dp[i][j-item.weight]+item.value   背包剩余的容量的最大价值 +当前物品的最大价值
                    dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
                } // 背包的容量 < 物品的容量时 则保留上一次的最大值不变
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[total];
    }



    //  打印数组的方法
    static void print(int[][] dp) {
        // 使用 StringBuilder 构造分隔线
        StringBuilder separator = new StringBuilder("   ");
        for (int i = 0; i < 63; i++) {
            separator.append("-");
        }
        System.out.println(separator);

        // 打印列的索引
        Object[] array = IntStream.range(0, dp[0].length).boxed().toArray();
        printArray(array);

        // 打印每行数据
        for (int[] d : dp) {
            array = Arrays.stream(d).boxed().toArray();
            printArray(array);
        }
    }

    private static void printArray(Object[] array) {
        for (Object obj : array) {
            System.out.printf("%5d ", obj);
        }
        System.out.println();
    }


}
